#ifndef HEAP_SORT_H_
#define HEAP_SORT_H_

#include <iostream>
using namespace std;

template<class Type>
class MaxHeap {
private:
    int _size;
	Type *_array;
	
public:
    MaxHeap(Type *array, int size);
	void buildHeap();
	void siftDown(int index);
	void swap(Type &ix, Type &jy);
	void removeMax();
	int leftChild(int index)  { return index * 2 + 1; }
	int rightChild(int index) { return index * 2 + 2; }
};

template<class Type>
inline MaxHeap<Type>::
MaxHeap(Type *array, int size)
{
	this->_array = array;
	_size = size;
	buildHeap();
}

template<class Type>
inline void MaxHeap<Type>::
buildHeap()
{
	for (int ix = _size/2; ix >= 0; ix--)
		siftDown(ix);
}

template<class Type>
inline void MaxHeap<Type>::
siftDown(int index)
{
	int max_index = leftChild(index);
	while (max_index < _size) {
		if (max_index + 1 < _size && _array[rightChild(index)] > _array[max_index])
			max_index ++;
		if (_array[index] > _array[max_index])
			break;
		swap(_array[index], _array[max_index]);
		index = max_index;
		max_index = leftChild(index);
	}
}

template<class Type>
inline void MaxHeap<Type>::
swap(Type &ix, Type &jy)
{
	Type temp;
	
	temp = ix;
	ix = jy;
    jy = temp;	
}

template<class Type>
inline void MaxHeap<Type>::
removeMax()
{
	while (_size > 0) {
		swap(_array[0], _array[_size - 1]);
	    _size --;
	    siftDown(0);
	}
}

#endif